1. Field of the Invention
The present invention relates generally to an absolute value arithmetic unit for integrated circuits. More particularly, the present invention relates to a high-speed absolute value arithmetic unit utilizing an area-efficient architecture having direct applications in floating point arithmetic.
2. Related Art
Today's personal computers are increasingly being cast into a role that once belonged only to supercomputers. In order to take on this role computers must be able to perform "number crunching" operations quickly and efficiently. In order to perform quickly, high speed arithmetic units are needed. In order to perform efficiently, minimal area should be used to implement a particular mathematical function. One growing area of importance in computer applications is floating point arithmetic.
Floating-point arithmetic expands the range of values over fixed-point arithmetic and assures a specific degree of accuracy for values over this wide numerical range. Arithmetic operations employing floating-point numbers are typically more complicated than the same operations using fixed-point numbers.
A floating-point number is a number n represented by two sets of numbers: the first set being a fixed point part m, and the second set being a radix (base number) r, and an exponent e. Thus: n=m.times.r.sup.e. The fixed part m is often referred to as the "mantissa." Both m and e can be positive or negative. Generally, the exponent indicates the magnitude of a number. For a more detailed explanation of floating-point systems, see Digital Computer Arithmetic: Design and Implementation, Cavanagh, McGraw-Hill Book Company, chapter 6 (1984) incorporated by reference.
In order to add or subtract two numbers in floating-point notation it is necessary to have the same order of magnitude for the exponents. For example, to add
______________________________________ 1.752 .times. 10.sup.3 (Example 1) +5.331 .times. 10.sup.4 ______________________________________
requires manipulation of the exponent to yield
______________________________________ 0.1752 .times. 10.sup.4 (Example 1) +5.331 .times. 10.sup.4 ______________________________________
As shown in Example 1, the smaller exponent is incremented to be the same as the larger exponent. Then the mantissa is shifted to the right one position so that the actual value of the number remains the same. Now, it is possible to add these two numbers in straight order fashion.
The function of shifting the fraction and scaling of the exponent occurs frequently in floating-point operations. The general rule implemented by most floating-point systems is to manipulate the smaller of the two numbers to be added or subtracted and leave the larger value alone. In order to adhere to this general rule it is necessary to know which number is bigger and how much to manipulate the smaller number. Accordingly, this is one function of an absolute value subtractor.
Another function of an absolute value subtractor is to determine which mantissa is larger. As shown in Example 2, the exponents are equal in value, but until subtraction is performed it is not known which mantissa is larger:
______________________________________ 7.54 .times. 10.sup.2 (Example 2) -9.32 .times. 10.sup.2 ______________________________________
In this situation, it is desirable to obtain a positive result, because the IEEE floating point format requires a positive valued unsigned integer format. If the result were negative, an extra 2's compliment arithmetic step will need to be performed. This wastes valuable time. To avoid this situation an absolute value subtractor is used to ensure that the difference is positive when the exponents are equal.
There are generally two types of conventional absolute value subtractors. The first type of absolute value subtractor optimizes speed, but requires a tremendous amount of chip area. The second type of absolute value subtractor requires less chip area, but is slow.
A. Absolute Value Subtractor 1
FIG. 1 illustrates a first type of a conventional absolute value subtractor 102. Absolute value subtractor 102 includes: two adders/subtractors 104, 106, and a multiplexer 110. Adder/subtractor 104, 106 are defined in section C below.
The operation of absolute value subtractor 102 involves performing two subtractions: A-B and B-A. The results, R1 and R2, from subtractors 104, 106, respectively, are selected on basis of whether there is a carry out from subtractor 104. R1 is selected if A.gtoreq.B and R2 is selected if B&gt;A. Multiplexer 110 selects the appropriate result Rn from adders/subtractors 104, 106 to obtain .vertline.A-B.vertline..
The drawback with absolute value subtractor 102 is that it uses two adder/subtractors 104, 106. A subtractor is generally much larger than a multiplexer. As a result, the cost of absolute value subtractor 102 in terms of chip area is significant.
B. Absolute Value Subtractor 2
FIG. 2 illustrates a second type of absolute value subtractor 202. Absolute value subtractor 202 includes: an adder/subtractor 204, an inverter 208, an incrementer 210 and a multiplexer 212. Adder/subtractor 204 are defined in section C below. The operation of absolute value subtractor 202 is self-evident from FIG. 2. Either adder/subtractor 204 produces a borrow or a no borrow condition after performing A-B. If A-B does not produce a borrow, then a carry out signal will indicate to multiplexer 212 to select the "A.gtoreq.B" branch 222 from adder/subtractor 204 to produce .vertline.A-B.vertline.. Data from subtractor 204 will follow the "B&gt;A" branch 224 from adder/subtractor 204 if there is a borrow condition. In a borrow condition state, the 2's complement is performed by inverter 208 and incrementer 210 to obtain .vertline.A-B.vertline..
The drawback with absolute value subtractor 202 is its slow speed. It is generally much slower than absolute value subtractor 102, because the "B&gt;A" data path requires data to pass through a great deal more elements than absolute value subtractor 102.
C. Subtractor defined
A subtractor is a combinational logic circuit. It can be expressed in terms of logical formula whose form describes an adder. How these logical equations are implemented as a circuit is the critical factor. As will be seen, the equations for addition are easily modified in terms of subtraction. For example, the sum of two numbers A and B is commonly expressed as: EQU (A+B).sub.i =A.sub.i XOR B.sub.i XOR C.sub.i-1 ( 1.0)
whereas the difference of A and B is commonly expressed as: EQU (A-B).sub.i =A.sub.i XOR (NOT B.sub.i) XOR C.sub.i-1 ( 1.2)
Basically, the only difference between A+B and A-B is that in equation (1.2) the B term is NOTed. Other than that equations (1.0) and (1.2) are closely related. Therefore, terms such as "adder/subtractor" and "sum/difference" are often interchanged, because addition and subtraction in digital format are essentially identical, (as can be seen by inspection of equations (1.0) and (1.2)). Hereinafter, reference will be made to subtraction.
The common uncertainty with equation (1.0) and (1.2) is that although values of A.sub.i and B.sub.i are known, the value of the carry term for a previous bit, C.sub.i-1, remains to be determined.
The carry out of bit i, C.sub.i, can be determined by equation (1.5) shown below. Terms g.sub.i and p.sub.i represent generate and propagate encodings of operands A and B. For subtraction, g.sub.i =A.sub.i B.sub.i and p.sub.i =A.sub.i XOR (NOT B.sub.i). For a general background discussion of propagate and generate signals see J. Hennessy et al. Computer Architecture a Quantitative Approach, Appendix A, pp. A-32-40 Morgan Kaufmann Publishers Inc. (1990) incorporated by reference; and J. F. Cavanagh, Digital Computer Arithmetic: Design and Implementation, Chapter 2 McGraw Hill (1984), incorporated by reference. EQU C.sub.i =g.sub.i +p.sub.i C.sub.i-1 ( 1.5)
As can be seen, for bit 0, equation (1.5), becomes C.sub.0 =g.sub.0 +p.sub.0 C.sub.in, and for bit 1, equation (1.5) becomes C.sub.1 =g.sub.1 +p.sub.1 (g.sub.0 +p.sub.0 C.sub.in) and so forth for every bit i. C.sub.i becomes more and more complicated as i increases, as illustrated in equation (1.6): EQU C.sub.i =[g.sub.i +(p.sub.i g.sub.i-1 +p.sub.i p.sub.i-1 g.sub.i-2 +p.sub.i p.sub.i-1 p.sub.i-2 g.sub.i-3 + . . . +g.sub.0)+(p.sub.i p.sub.i-1 -p.sub.i-2 . . . p.sub.0)]C.sub.in ( 1.6)
Different methods exist to determine C.sub.i. One of the most popular is a carry look ahead approach. Conventional subtractor 104, 106, and 204 (sometimes referred to as carry-lookahead adders CLAs) implement the above-mentioned equations. Such a subtractor is able to obtain the difference of A and B and is the main component of an absolute value subtractor. In order to better understand the present invention, it is necessary to inspect a conventional subtractor 104, 106, 204.
FIG. 3A illustrates a carry-lookahead subtractor 104, 106, 204. The adder is comprised of two main sections: a section 310 produces propagate (p) and generate (g) terms; and a second section 312 utilizes the propagate and generate signals of first section 310 to produce a plurality of carry signals to be summed in the first stage 310 (shown as D.sub.s).
Referring to FIG. 3A, inputs A7-A0 and B7-B0 are converted to p's and g's using a plurality of propagate-and-generate/summer cells 302. The various p's and g's, p.sub.7 -p.sub.0 and g.sub.7 -g.sub.0, are combined in carry-chain-cells 304 to produce further P's and G's. Notice that small p's and g's are used to denote signals from propagate-and-generate cells 302 and capitalized P's and G's are used to denote carry-chain-cells 304. As shown in FIG. 3A, the equations for propagate-and-generate/summer cell 302 and carry-chain-cell 304 are illustrated in FIGS. 3B and 3C, respectively.
Generally, referring to FIG. 3A, operands A and B enter at the top of subtractor 104, 106, 204. The signals produced as a result of these inputs flow from the top of subtractor 104, 106, 204 downward through the carry-chain-cells 304, combine with the carry in of bit 0, C.sub.in, at the bottom of section 312 at carry-chain-cell 304. Then signals flow back up subtractor 104, 106, 204 to form a plurality of carries which are added together to produce the difference D7-D1.
There are a number of problems with carry lookahead subtractor 104, 106, 204, which limit its efficiency. First, as a major component of an absolute value arithmetic unit, it is limited to producing only one core subtraction, either A-B or B-A (the carry-in is fixed at zero or one i.e., see equations above and fix Cin at 0 or 1). Second, its carry-chain 312 and propagate-and-generate/summer 302 provide a minimal amount of information regarding propagate and generate terms. In other words, carry-chain 312 only provides carry out information for each bit. Third, subtraction/addition is performed in a convoluted inefficient way. The data flow is first fed down and then up the adder/subtractor resulting in more wires. In general data flow is better in one direction because wiring can be minimized. Additionally, many logic instructions are performed in a dense area making the design unnecessarily complicated.
D. Summary of the problem
Currently absolute value subtractors are available, but they are slow and/or large in area (large area usually results in more power consumption). Therefore, what is needed is an absolute value subtractor which is as fast as, or faster than, absolute value subtractors 102, 202 and is smaller than either of absolute value subtractors 102, 202 and requires less power.